{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. 冒泡排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import iplantuml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing output for /home/jack/Desktop/structures-algorithms/f6e0d688-d32b-4c7c-9f33-306a7bace117.uml to f6e0d688-d32b-4c7c-9f33-306a7bace117.svg\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" contentStyleType=\"text/css\" height=\"344px\" preserveAspectRatio=\"none\" style=\"width:281px;height:344px;background:#FFFFFF;\" version=\"1.1\" viewBox=\"0 0 281 344\" width=\"281px\" zoomAndPan=\"magnify\"><defs/><g><ellipse cx=\"145.3545\" cy=\"20\" fill=\"#222222\" rx=\"10\" ry=\"10\" style=\"stroke:#222222;stroke-width:1.0;\"/><rect fill=\"#F1F1F1\" height=\"33.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"164.709\" x=\"63\" y=\"210.5151\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"144.709\" x=\"73\" y=\"231.6538\">a[j],a[j+1] = a[j+1], a[j]</text><polygon fill=\"#F1F1F1\" points=\"110.762,166.5151,179.947,166.5151,191.947,178.5151,179.947,190.5151,110.762,190.5151,98.762,178.5151,110.762,166.5151\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"69.1851\" x=\"110.762\" y=\"182.3232\">a[j] &gt; a[j+1]</text><polygon fill=\"#F1F1F1\" points=\"145.3545,264.4839,157.3545,276.4839,145.3545,288.4839,133.3545,276.4839,145.3545,264.4839\" style=\"stroke:#181818;stroke-width:0.5;\"/><polygon fill=\"#F1F1F1\" points=\"111.5461,110.8047,179.1628,110.8047,191.1628,122.8047,179.1628,134.8047,111.5461,134.8047,99.5461,122.8047,111.5461,110.8047\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"24.981\" x=\"149.3545\" y=\"145.0151\">True</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"67.6167\" x=\"111.5461\" y=\"126.6128\">j in [0, n-1-i)</text><polygon fill=\"#F1F1F1\" points=\"115.0588,50,175.6501,50,187.6501,62,175.6501,74,115.0588,74,103.0588,62,115.0588,50\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"24.981\" x=\"149.3545\" y=\"84.2104\">True</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"60.5913\" x=\"115.0588\" y=\"65.8081\">i in [0, n-1)</text><ellipse cx=\"24\" cy=\"109\" fill=\"none\" rx=\"11\" ry=\"11\" style=\"stroke:#222222;stroke-width:1.0;\"/><ellipse cx=\"24\" cy=\"109\" fill=\"#222222\" rx=\"6\" ry=\"6\" style=\"stroke:#222222;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"190.5151\" y2=\"210.5151\"/><polygon fill=\"#181818\" points=\"141.3545,200.5151,145.3545,210.5151,149.3545,200.5151,145.3545,204.5151\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"191.947\" x2=\"237.709\" y1=\"178.5151\" y2=\"178.5151\"/><polygon fill=\"#181818\" points=\"233.709,217.4995,237.709,227.4995,241.709,217.4995,237.709,221.4995\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"237.709\" x2=\"237.709\" y1=\"178.5151\" y2=\"276.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"237.709\" x2=\"157.3545\" y1=\"276.4839\" y2=\"276.4839\"/><polygon fill=\"#181818\" points=\"167.3545,272.4839,157.3545,276.4839,167.3545,280.4839,163.3545,276.4839\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"244.4839\" y2=\"264.4839\"/><polygon fill=\"#181818\" points=\"141.3545,254.4839,145.3545,264.4839,149.3545,254.4839,145.3545,258.4839\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"134.8047\" y2=\"166.5151\"/><polygon fill=\"#181818\" points=\"141.3545,156.5151,145.3545,166.5151,149.3545,156.5151,145.3545,160.5151\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"288.4839\" y2=\"298.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"255.709\" y1=\"298.4839\" y2=\"298.4839\"/><polygon fill=\"#181818\" points=\"251.709,219.0972,255.709,209.0972,259.709,219.0972,255.709,215.0972\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"255.709\" x2=\"255.709\" y1=\"122.8047\" y2=\"298.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"255.709\" x2=\"191.1628\" y1=\"122.8047\" y2=\"122.8047\"/><polygon fill=\"#181818\" points=\"201.1628,118.8047,191.1628,122.8047,201.1628,126.8047,197.1628,122.8047\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"99.5461\" x2=\"49\" y1=\"122.8047\" y2=\"122.8047\"/><polygon fill=\"#181818\" points=\"45,205.0972,49,215.0972,53,205.0972,49,209.0972\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"49\" x2=\"49\" y1=\"122.8047\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"49\" x2=\"267.709\" y1=\"310.4839\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"267.709\" x2=\"267.709\" y1=\"62\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"267.709\" x2=\"187.6501\" y1=\"62\" y2=\"62\"/><polygon fill=\"#181818\" points=\"197.6501,58,187.6501,62,197.6501,66,193.6501,62\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"74\" y2=\"110.8047\"/><polygon fill=\"#181818\" points=\"141.3545,100.8047,145.3545,110.8047,149.3545,100.8047,145.3545,104.8047\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"103.0588\" x2=\"24\" y1=\"62\" y2=\"62\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"24\" x2=\"24\" y1=\"62\" y2=\"98\"/><polygon fill=\"#181818\" points=\"20,88,24,98,28,88,24,92\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"145.3545\" x2=\"145.3545\" y1=\"30\" y2=\"50\"/><polygon fill=\"#181818\" points=\"141.3545,40,145.3545,50,149.3545,40,145.3545,44\" style=\"stroke:#181818;stroke-width:1.0;\"/><!--SRC=[Aov9B2hXAi_8p4dLo5J8p5E8Dj1HoDCrrDJCBDO8AIfDrUHI00A8WYma1RgPQ4f083DDGICnEYjMmKu1I6aRnYAaGC0A9AS3aL6mXIhH0T6nrd25gNafcMbSK1RONYuuexWalm00]--></g></svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%plantuml\n",
    "@startuml\n",
    "start\n",
    "while(i in [0, n-1))is(True)\n",
    "    while(j in [0, n-1-i))is(True)\n",
    "        if (a[j] > a[j+1])\n",
    "            :a[j],a[j+1] = a[j+1], a[j];\n",
    "        endif\n",
    "    endwhile\n",
    "endwhile\n",
    "stop\n",
    "@enduml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "def 冒泡排序(序列):\n",
    "    长度 = len(序列)\n",
    "    for i in range(0, 长度 - 1):\n",
    "        for j in range(0, 长度 - 1 - i):\n",
    "            if  序列[j] > 序列[j+1]:\n",
    "                序列[j], 序列[j+1] = 序列[j+1], 序列[j]\n",
    "    return 序列\n",
    "\n",
    "结果 = 冒泡排序([5, 3, 9, 6, 8, 2, 7])\n",
    "print(结果)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. 选择排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing output for /home/jack/Desktop/structures-algorithms/073d52db-34ad-4960-9712-ff4b270bd64a.uml to 073d52db-34ad-4960-9712-ff4b270bd64a.svg\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" contentStyleType=\"text/css\" height=\"344px\" preserveAspectRatio=\"none\" style=\"width:250px;height:344px;background:#FFFFFF;\" version=\"1.1\" viewBox=\"0 0 250 344\" width=\"250px\" zoomAndPan=\"magnify\"><defs/><g><ellipse cx=\"129.5723\" cy=\"20\" fill=\"#222222\" rx=\"10\" ry=\"10\" style=\"stroke:#222222;stroke-width:1.0;\"/><rect fill=\"#F1F1F1\" height=\"33.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"133.1445\" x=\"63\" y=\"210.5151\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"113.1445\" x=\"73\" y=\"231.6538\">a[i], a[j] = a[j], a[i]</text><polygon fill=\"#F1F1F1\" points=\"103.0874,166.5151,156.0571,166.5151,168.0571,178.5151,156.0571,190.5151,103.0874,190.5151,91.0874,178.5151,103.0874,166.5151\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"52.9697\" x=\"103.0874\" y=\"182.3232\">a[i] &gt; a[j]</text><polygon fill=\"#F1F1F1\" points=\"129.5723,264.4839,141.5723,276.4839,129.5723,288.4839,117.5723,276.4839,129.5723,264.4839\" style=\"stroke:#181818;stroke-width:0.5;\"/><polygon fill=\"#F1F1F1\" points=\"98.624,110.8047,160.5205,110.8047,172.5205,122.8047,160.5205,134.8047,98.624,134.8047,86.624,122.8047,98.624,110.8047\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"24.981\" x=\"133.5723\" y=\"145.0151\">True</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"61.8965\" x=\"98.624\" y=\"126.6128\">j in [i+1, n)</text><polygon fill=\"#F1F1F1\" points=\"99.2766,50,159.8679,50,171.8679,62,159.8679,74,99.2766,74,87.2766,62,99.2766,50\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"24.981\" x=\"133.5723\" y=\"84.2104\">True</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"60.5913\" x=\"99.2766\" y=\"65.8081\">i in [0, n-1)</text><ellipse cx=\"24\" cy=\"109\" fill=\"none\" rx=\"11\" ry=\"11\" style=\"stroke:#222222;stroke-width:1.0;\"/><ellipse cx=\"24\" cy=\"109\" fill=\"#222222\" rx=\"6\" ry=\"6\" style=\"stroke:#222222;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"190.5151\" y2=\"210.5151\"/><polygon fill=\"#181818\" points=\"125.5723,200.5151,129.5723,210.5151,133.5723,200.5151,129.5723,204.5151\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"168.0571\" x2=\"206.1445\" y1=\"178.5151\" y2=\"178.5151\"/><polygon fill=\"#181818\" points=\"202.1445,217.4995,206.1445,227.4995,210.1445,217.4995,206.1445,221.4995\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"206.1445\" x2=\"206.1445\" y1=\"178.5151\" y2=\"276.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"206.1445\" x2=\"141.5723\" y1=\"276.4839\" y2=\"276.4839\"/><polygon fill=\"#181818\" points=\"151.5723,272.4839,141.5723,276.4839,151.5723,280.4839,147.5723,276.4839\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"244.4839\" y2=\"264.4839\"/><polygon fill=\"#181818\" points=\"125.5723,254.4839,129.5723,264.4839,133.5723,254.4839,129.5723,258.4839\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"134.8047\" y2=\"166.5151\"/><polygon fill=\"#181818\" points=\"125.5723,156.5151,129.5723,166.5151,133.5723,156.5151,129.5723,160.5151\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"288.4839\" y2=\"298.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"224.1445\" y1=\"298.4839\" y2=\"298.4839\"/><polygon fill=\"#181818\" points=\"220.1445,219.0972,224.1445,209.0972,228.1445,219.0972,224.1445,215.0972\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"224.1445\" x2=\"224.1445\" y1=\"122.8047\" y2=\"298.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"224.1445\" x2=\"172.5205\" y1=\"122.8047\" y2=\"122.8047\"/><polygon fill=\"#181818\" points=\"182.5205,118.8047,172.5205,122.8047,182.5205,126.8047,178.5205,122.8047\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"86.624\" x2=\"49\" y1=\"122.8047\" y2=\"122.8047\"/><polygon fill=\"#181818\" points=\"45,205.0972,49,215.0972,53,205.0972,49,209.0972\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"49\" x2=\"49\" y1=\"122.8047\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"49\" x2=\"236.1445\" y1=\"310.4839\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"236.1445\" x2=\"236.1445\" y1=\"62\" y2=\"310.4839\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"236.1445\" x2=\"171.8679\" y1=\"62\" y2=\"62\"/><polygon fill=\"#181818\" points=\"181.8679,58,171.8679,62,181.8679,66,177.8679,62\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"74\" y2=\"110.8047\"/><polygon fill=\"#181818\" points=\"125.5723,100.8047,129.5723,110.8047,133.5723,100.8047,129.5723,104.8047\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"87.2766\" x2=\"24\" y1=\"62\" y2=\"62\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"24\" x2=\"24\" y1=\"62\" y2=\"98\"/><polygon fill=\"#181818\" points=\"20,88,24,98,28,88,24,92\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"129.5723\" x2=\"129.5723\" y1=\"30\" y2=\"50\"/><polygon fill=\"#181818\" points=\"125.5723,40,129.5723,50,133.5723,40,129.5723,44\" style=\"stroke:#181818;stroke-width:1.0;\"/><!--SRC=[Aov9B2fHu2hFoCn9rSXKoCnJY3RGKSZJDTJKp2pM22agJTNaKW02Y88ii89CRKEW4ZG5892Pff4OdHchOAUG69qLYn070IkGZ0vOGi4MJ84ucR7MS5MfUIcPQLnG5jW-BZYZk2I_0000]--></g></svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%plantuml \n",
    "@startuml\n",
    "start \n",
    "while(i in [0, n-1))is(True)\n",
    "    while(j in [i+1, n))is(True)\n",
    "        if(a[i] > a[j])\n",
    "            :a[i], a[j] = a[j], a[i];\n",
    "        endif\n",
    "    endwhile\n",
    "endwhile\n",
    "stop\n",
    "@enduml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "def 选择排序(序列: list):\n",
    "    n = len(序列)\n",
    "    for i in range(0, n-1):\n",
    "        for j in range(i+1, n):\n",
    "            if 序列[i] > 序列[j]:\n",
    "                序列[i], 序列[j] = 序列[j], 序列[i]\n",
    "    return 序列 \n",
    "\n",
    "结果 = 选择排序([5, 3, 9, 6, 8, 2, 7])\n",
    "print(结果)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
